package leetcode.Fiftyone_to_One_hundred;

import java.util.ArrayList;
import java.util.List;

/**
 * 98. 验证二叉搜索树
 */
public class Test98 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // 中序遍历的结果要是递增的
    List<Integer> list = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
       if (root != null) {
           isValidBST(root.left);
           list.add(root.val);
           isValidBST(root.right);
       } else {
           return true;
       }
       return isIncrease(list);
    }

    public boolean isIncrease(List<Integer> list) {
        if (list.size() > 0) {
            int firstElement = list.get(0);
            for (int i = 1; i < list.size(); i++) {
                if (list.get(i) <= firstElement) {
                    return false;
                }
                firstElement = list.get(i);
            }
        } else {
            return false;
        }
        return true;
    }
}

/**
 * if (root.left != null && root.left.val >= root.val
 *                 || root.right != null && root.right.val <= root.val) {
 *             return false;
 *         }
 *         return isValidBST(root.left) && isValidBST(root.right);
 */